1. Field of the Invention
This invention relates generally to optimum route determination. In particular, this invention relates to a method and corresponding system for pre-processing road segment data, a method and corresponding system for determining an optimum route based on pre-processed road segment data, and a navigation system.
2. Related Art
Finding an optimum route from a given start point to a given destination point is one of the key functions of car navigation systems or other systems providing optimum route information.
While several algorithms are known for solving the problem of finding an optimum route, it is often not feasible to apply these algorithms directly to a road network such as found in a European country or the United States because of the large number of road segments and road segment vertices in these road networks. The number of vertices may well be of the order or in excess of one million. Because of memory and runtime restrictions in a car navigation system, it is therefore not feasible to directly employ standard shortest path algorithms to a long-distance optimum route search.
When road networks have a natural hierarchical structure expressed by road classes, such as “Autobahn”, “Bundesstraβe”, and “Kreisstraβe” in Germany, or “Motorway”, “A road”, and “B road” in the UK, these road classes may be used to reduce the complexity of optimum route search. The determination of an optimum route may be broken down into several subtasks, namely: A) the tasks of finding a short-distance route from the start point to an opportunity for high speed travel such as a motorway junction or a junction of another road allowing fast long-distance travel; B) finding a short-distance route from the destination to another motorway junction or a junction of another road allowing fast long-distance travel; and C) the task of finding an optimum route between these two motorway junctions using motorways or other roads allowing fast long-distance travel only.
A hierarchical structure of the road network is also reflected by maps having the standardized GDF (Geographic Data File) format, in which all road segments have an attribute called Functional Road Class (FRC) which defines a hierarchy of roads and is intended to distinguish roads of local importance from those of national or international importance.
However, it should be noted that, because the hierarchical structure of road segments is assigned by a human expert, the determined route may not be truly optimum. Furthermore, it may not be sufficient to rely on standard road hierarchies such as the FRC that target fastest routes and, therefore, may be inappropriate for computing shortest routes or other routing options. Values quantifying road importance that are assigned by human experts may therefore be insufficient. Thus, it would be useful to augment the prior art with a method for determining a road segment attribute from map geometry. In particular, there is remains a need for a method for determining optimum routes in which such road segment attributes may be determined efficiently, even for large road networks.